Abstraction: There is a graph, with nodes and edges. Abstraction involves focusing on what is important and ignoring the rest - for example, we have not shown how much each tourist attraction cost for entry.
Generalization: Both problems are similar problems - ask students in what respect. Both problems involved going from one point to all other points and coming back to the original problem.
Algorithm: The method to solve the problem. How did you go about traversing the graph? For this kind of the problem, depth first is an intuitive route - you go down a path as far as you can and you backtrack if its the wrong path and try another one.
Pattern Matching: It seems that we can solve any "route finding" problem by drawing a graph for that - this is pattern matching.
Patterns we have looked at so far
Binary Search
Sorting
Induction/ Recursion
Today we will look at another pattern - pigeon hole principle
(MC - Chapter 4)
Explain basic Pigeonhole principle: If we put N+1 or more pigeons into N pigeon holes, then some pigeon hole must contain two or more pigeons.
A bag contains beads of two colors: black and white. What is the smallest number of beads which must be drawn so that there are two of the same color?
Answer: 3 - Explain in terms of what is the pigeon and what is the pigeon hole
One million pine trees grow in a forest. Each pine tree has up to 600,000 needles on it. Show that at least two pine tress must have the same number of needles
Explain in terms of pigeon and pigeon hole
(Hav 2007) - People are seated around a circular table at a restaurant. The food is placed on a circular platform in the center of the table and this circular platform can rotate. Each person ordered a different entrée, and it turns out that no one has the correct entrée in front of him. Show that it is possible to rotate the platform so that at least two people will have the correct entrée
Number of rotations (n-1), number of matches n, hence at least two in one. Explain in terms of pigeons and pigeon holes.
Given twelve integers, show that two of them can be chosen whose difference is divisible by 11
Can you generalize to n numbers? What is the pigeon and what is the pigeon hole?
Homework:
(Hav 2007) Seven points are placed inside a regular hexagon of side length 1. Show that at least two points are at most 1 unit apart
Partition the hexagon into 6 equal triangles. The diameter of each triangle (maximum distance between any two points within the triangle) is 1. At least one triangle must contain two points, hence proved.
References:
Mathematical Circles (Russian Experience), by Dmitri Fomin, Sergey Genkin, Ilia Itenberg